package com.str;

public class RepeatedSubStringPatterm0202_459 {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int l = len - getNext(s,len-1);
        return len != l && len % l == 0;
    }

    //最长相等前后缀
    private int getNext(String s, int i) {
        int[] next = new int[s.length()];
        next[0] = 0;
        int j = 0;
        for (int k = 1; k < s.length(); k++) {
            while (j>0 && s.charAt(j) != s.charAt(k)) j=next[j-1];
            if(s.charAt(j) == s.charAt(k)) j++;
            next[k] = j;
        }
        return next[i];
    }
}
